package com.sx.sx1.lintcode.day717;

import org.apache.tomcat.util.net.jsse.JSSEUtil;

public class LC3633 {

    static class Solution {
        /**
         * @param arr: the arithmetic progression array
         * @return: the missing number
         */
        public int missingNumber(int[] arr) {
            int n= arr.length;
            int diff1 =0,diff2=0,cnt1=0,cnt2=0,pos1=-1,pos2=-1;
            for (int i = 1; i < n; i++) {
                int diff = arr[i]-arr[i-1];

                if(diff1==0 || diff == diff1){
                    diff1 = diff;
                    cnt1++;
                    pos1=i;
                }else if(diff2==0 || diff==diff2){
                    diff2 = diff;
                    cnt2++;
                    pos2=i;
                }
            }

            if(cnt1==1) {
                return arr[pos1] - diff2;
            }else{
                return arr[pos2]-diff1;
            }
        }
    }

    public static void main(String[] args) {
        Solution obj = new Solution();
        System.out.println(obj.missingNumber(new int[]{2,5,8,14}));
        System.out.println(obj.missingNumber(new int[]{1,2,4,5}));
        System.out.println(obj.missingNumber(new int[]{5, 0, -10, -15}));
    }

}


/*
LintCode-Logo
搜索题目、标签、题集
中文
avatar
您有214条未读消息，请及时查看
3633 · 等差数列中缺失的数字
算法
简单
通过率
59%

题目
题解17
笔记
讨论1
排名
记录
描述
存在一个数组 arr，其所有元素可构成等差数列。

等差数列：
𝑎
𝑟
𝑟
𝑛
=
𝑎
𝑟
𝑟
1
+
(
𝑛
−
1
)
𝑑
arr
n
​
 =arr
1
​
 +(n−1)d，即
𝑎
𝑟
𝑟
𝑛
+
1
−
𝑎
𝑛
=
𝑑
arr
n+1
​
 −a
n
​
 =d。其中
𝑑
d 为常数。

在本题中，等差 arr 被 从中间 删除了一个元素（既不是第一个，也不是最后一个），你需要找出并返回被删除的元素。

最短时间刷“透”算法面试：《66页算法宝典》.pdf

微信添加【jiuzhangfeifei】备注【66】领取


3
<
=
𝑎
𝑟
𝑟
.
𝑙
𝑒
𝑛
𝑔
𝑡
ℎ
<
=
100
3<=arr.length<=100

样例
样例 1

输入：

[2, 5, 8, 14]
输出：

11
样例 2

输入：

[1, 2, 4, 5]
输出：

3
样例 3

输入：

[5, 0, -10, -15]
输出：

-5
样例 4

输入：

[10, 8, 7]
输出：

9
解释：

原来的数组是 [10, 9, 8, 7]
标签
推荐课程

简历/BQ/项目 面试软技能指导
FLAG高级工程师深度BQ辅导，简历打造+1V1模拟面试，反面试套路、高效上岸！
150/1859
已开启智能提示
发起考试
15 分 00 秒
123456789

控制台
        历史提交

 */